public class IsPalindrome {
    // leetcode 回文链表
    // https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
    public boolean isPalindrome(ListNode head) {
        // 先找到链表的中间节点，然后将后半部分的链表进行逆转，然后比较前半部分链表是否和后半部分的相同
        ListNode slow = head, fast = head;
        // 找到中间节点
        while (fast.next != null && fast.next != null) {
            fast = fast.next.next;
            if (fast == null) break;
            slow = slow.next;
        }
        // 将后半部分的链表进行翻转
        ListNode prev = null, cur = slow.next;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        while (head != null && prev != null) {
            if (head.val != prev.val) return false;
            head = head.next;
            prev = prev.next;
        }
        return true;
    }
}
